﻿#region MIT
/*
Engine Of Evermore (http://code.google.com/p/engineofevermore/)
Copyright (c) 2008, 2009 Michael Woerister

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#endregion

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;

namespace EngineOfEvermore.Common
{
    public sealed class BinaryHeap<T> : IEnumerable<T>, IEnumerable, ICollection
    {
        #region Constructors
        public BinaryHeap()
        {
            _items = new T[DEFAULT_CAPACITY];
            _comparer = Comparer<T>.Default;
        }

        public BinaryHeap( Comparer<T> comparer )
        {
            Debug.Assert( comparer != null );

            _items = new T[DEFAULT_CAPACITY];
            _comparer = comparer;
        }

        public BinaryHeap( int initialCapacity )
        {
            if ( initialCapacity < 0 )
            {
                throw new ArgumentOutOfRangeException();
            }

            _items = new T[initialCapacity];
            _comparer = Comparer<T>.Default;
        }

        public BinaryHeap( IEnumerable<T> collection )
        {
            Debug.Assert( collection != null );

            _items = new T[DEFAULT_CAPACITY];
            _comparer = Comparer<T>.Default;

            foreach ( T item in collection )
            {
                Enqueue( item );
            }
        }

        public BinaryHeap( BinaryHeap<T> other )
        {
            Debug.Assert( other != null );

            _items = new T[other._items.Length];

            for ( int i = 0; i < _items.Length; ++i )
            {
                _items[i] = other._items[i];
            }

            _itemCount = other._itemCount;
            _comparer = other._comparer;
        }
        #endregion

        #region Properties
        public int Count
        {
            get { return _itemCount; }
        }

        public int Capacity
        {
            get { return _items.Length; }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return this; }
        }
        #endregion

        #region Public Methods
        public void Enqueue( T item )
        {
            // Check capacity
            if ( _items.Length == _itemCount )
            {
                _expandCapacity();
            }

            int bubbleIndex = _itemCount;
            _items[_itemCount++] = item;

            _perlocateUp( bubbleIndex );
        }

        public T Dequeue()
        {
            if ( _itemCount == 0 )
            {
                throw new InvalidOperationException( "Item count is zero" );
            }

            T removedItem = _items[0];

            int minIndexTouched, maxIndexTouched;
            _removeAt( 0, out minIndexTouched, out maxIndexTouched );

            return removedItem;
        }

        public T Peek()
        {
            if ( _itemCount == 0 )
            {
                throw new InvalidOperationException( "Item count is zero" );
            }

            return _items[0];
        }

        public bool Remove( T item )
        {
            if ( _itemCount == 0 )
            {
                return false;
            }

            int itemIndex = 0;

            for ( ; itemIndex < _itemCount; ++itemIndex )
            {
                if ( _comparer.Compare( _items[itemIndex], item ) == 0 )
                    break;
            }

            if ( itemIndex == _itemCount )
            {
                return false;
            }

            int minIndexTouched, maxIndexTouched;
            _removeAt( itemIndex, out minIndexTouched, out maxIndexTouched );

            return true;
        }

        public int RemoveAll( Predicate<T> predicate )
        {
            if ( predicate == null )
                throw new ArgumentNullException();

            int i = 0;
            int removalCount = 0;

            while ( i < _itemCount )
            {
                if ( predicate( _items[i] ) )
                {
                    int minIndexTouched, maxIndexTouched;
                    _removeAt( i, out minIndexTouched, out maxIndexTouched );
                    ++removalCount;

                    if ( minIndexTouched < i )
                    {
                        i = minIndexTouched;
                    }
                }
                else
                {
                    ++i;
                }
            }

            return removalCount;
        }

        public bool Contains( T item )
        {
            return _items.Take( _itemCount ).Any( x => ( _comparer.Compare( x, item ) == 0 ) );
        }

        public void Clear()
        {
            // Clear all items, so they may be garbage collected
            for ( int i = 0; i < _itemCount; ++i )
            {
                _items[i] = default( T );
            }

            _itemCount = 0;
        }

        public void TrimExcess()
        {
            if ( _itemCount != _items.Length )
            {
                T[] newBuffer = new T[_itemCount];

                for ( int i = 0; i < newBuffer.Length; ++i )
                {
                    newBuffer[i] = _items[i];
                }

                _items = newBuffer;
            }
        }

        public IEnumerator<T> GetEnumerator()
        {
            return _items.Take( _itemCount ).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return _items.Take( _itemCount ).GetEnumerator();
        }

        public void CopyTo( Array array, int index )
        {
            if ( array == null )
                throw new ArgumentNullException( "array is null" );

            if ( index < 0 )
                throw new ArgumentOutOfRangeException( "index is less than zero" );

            if ( array.Rank != 1 )
                throw new ArgumentException( "array is not one-dimensional" );

            if ( index >= array.Length )
                throw new ArgumentException( "index is greater than or equal to array length" );

            if ( index + Count >= array.Length )
                throw new ArgumentException( "not enough space in array" );

            for ( int i = 0; i < Count; ++i )
            {
                array.SetValue( _items[i], index + i );
            }
        }
        #endregion

        #region Private Methods
        int _perlocateUp( int bubbleIndex )
        {
            while ( bubbleIndex != 0 )
            {
                int parentIndex = _parentIndex( bubbleIndex );

                if ( _comparer.Compare( _items[bubbleIndex], _items[parentIndex] ) < 0 )
                {
                    var temp = _items[parentIndex];
                    _items[parentIndex] = _items[bubbleIndex];
                    _items[bubbleIndex] = temp;
                    bubbleIndex = parentIndex;
                }
                else
                {
                    break;
                }
            }

            return bubbleIndex;
        }

        int _perlocateDown( int itemIndex )
        {
            int swapIndex = itemIndex;

            do
            {
                itemIndex = swapIndex;

                int firstChildIndex = _firstChildIndex( itemIndex );
                int seccondChildIndex = _secondChildIndex( itemIndex );

                if ( seccondChildIndex < _itemCount )
                {
                    // Both children exist
                    if ( _comparer.Compare( _items[itemIndex], _items[firstChildIndex] ) > 0 )
                    {
                        swapIndex = firstChildIndex;
                    }

                    if ( _comparer.Compare( _items[swapIndex], _items[seccondChildIndex] ) > 0 )
                    {
                        swapIndex = seccondChildIndex;
                    }
                }
                else if ( _firstChildIndex( itemIndex ) < _itemCount )
                {
                    // Only one child exists
                    if ( _comparer.Compare( _items[itemIndex], _items[firstChildIndex] ) > 0 )
                    {
                        swapIndex = firstChildIndex;
                    }
                }

                // One if the parent's children are smaller or equal, swap them
                if ( itemIndex != swapIndex )
                {
                    var temp = _items[itemIndex];
                    _items[itemIndex] = _items[swapIndex];
                    _items[swapIndex] = temp;
                }
                else
                {
                    break;
                }
            } while ( true );

            return itemIndex;
        }

        void _removeAt( int itemIndex, out int minIndexTouched, out int maxIndexTouched )
        {
            Debug.Assert( _itemCount > 0 );

            --_itemCount;

            if ( _itemCount == 0 )
            {
                Debug.Assert( itemIndex == 0 );

                _items[0] = default( T );
                minIndexTouched = 0;
                maxIndexTouched = 0;
            }
            else
            {
                Debug.Assert( itemIndex >= 0 && itemIndex <= _itemCount );

                if ( itemIndex == _itemCount )
                {
                    _items[_itemCount] = default( T );

                    minIndexTouched = itemIndex;
                    maxIndexTouched = itemIndex;
                }
                else
                {
                    _items[itemIndex] = _items[_itemCount];
                    _items[_itemCount] = default( T );

                    if ( itemIndex != 0 )
                    {
                        minIndexTouched = _perlocateUp( itemIndex );
                    }
                    else
                    {
                        minIndexTouched = 0;
                    }

                    maxIndexTouched = Math.Max( itemIndex, _perlocateDown( itemIndex ) );
                }
            }
        }

        void _expandCapacity()
        {
            if ( _items.Length != 0 )
            {
                T[] newBuffer = new T[_items.Length * 2];

                for ( int i = 0; i < _items.Length; ++i )
                {
                    newBuffer[i] = _items[i];
                }

                _items = newBuffer;
            }
            else
            {
                _items = new T[DEFAULT_CAPACITY];
            }
        }

        static int _parentIndex( int index )
        {
            return ( index - 1 ) / 2;
        }

        static int _firstChildIndex( int index )
        {
            return index * 2 + 1;
        }

        static int _secondChildIndex( int index )
        {
            return index * 2 + 2;
        }
        #endregion

        #region Variables
        const int DEFAULT_CAPACITY = 32;
        T[] _items;
        int _itemCount;
        readonly IComparer<T> _comparer;
        #endregion

        #region Debug and Validation Methods
        public static bool VerifyHeapProperty( BinaryHeap<T> heap )
        {
            for ( int i = 0; i < heap._itemCount; ++i )
            {
                int childIndex1 = _firstChildIndex( i );
                int childIndex2 = _secondChildIndex( i );

                if ( childIndex1 < heap._itemCount )
                {
                    if ( heap._comparer.Compare( heap._items[i], heap._items[childIndex1] ) > 0 )
                    {
                        return false;
                    }
                }

                if ( childIndex2 < heap._itemCount )
                {
                    if ( heap._comparer.Compare( heap._items[i], heap._items[childIndex2] ) > 0 )
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        public static bool FullIntegrityCheck( BinaryHeap<T> heap )
        {
            if ( heap._items == null )
            {
                return false;
            }

            if ( heap._itemCount < 0 )
            {
                return false;
            }

            if ( !( heap.Count <= heap.Capacity ) )
            {
                return false;
            }

            T defaultValue = default( T );

            for ( int i = heap.Count; i < heap.Capacity; ++i )
            {
                if ( heap._comparer.Compare( heap._items[i], defaultValue ) != 0 )
                {
                    return false;
                }
            }

            return VerifyHeapProperty( heap );
        }

        public static void PrintPretty( BinaryHeap<T> heap, StringBuilder builder, int indention )
        {
            heap._prettyPrinter( 0, 0, indention, builder );
        }

        void _prettyPrinter( int itemIndex, int totalIndent, int indent, StringBuilder builder )
        {
            if ( _firstChildIndex( itemIndex ) < _itemCount )
            {
                int firstChildIndex = _firstChildIndex( itemIndex );
                _prettyPrinter( firstChildIndex, totalIndent + indent, indent, builder );
            }

            builder.AppendLine();
            builder.Append( ' ', totalIndent );
            builder.Append( _items[itemIndex] );

            if ( _secondChildIndex( itemIndex ) < _itemCount )
            {
                int secondChildIndex = _secondChildIndex( itemIndex );
                _prettyPrinter( secondChildIndex, totalIndent + indent, indent, builder );
            }
        }
        #endregion
    }

    #region Unit Tests
    #if ENGINE_OF_EVERMORE_ENABLE_UNIT_TESTS
    namespace UnitTest
    {
        using NUnit.Framework;

        [TestFixture]
        public class BinaryHeapTest
        {
            [Test]
            public void TestWithDefaultCapacity()
            {
                const int ELEMENT_COUNT = 10000;
                BinaryHeap<int> heap = new BinaryHeap<int>();

                _defaultTest( heap, ELEMENT_COUNT );
            }

            [Test]
            public void TestWithZeroCapacity()
            {
                const int ELEMENT_COUNT = 10000;
                BinaryHeap<int> heap = new BinaryHeap<int>( 0 );

                _defaultTest( heap, ELEMENT_COUNT );
            }

            [Test]
            public void TestWithFullCapacity()
            {
                const int ELEMENT_COUNT = 10000;
                BinaryHeap<int> heap = new BinaryHeap<int>( ELEMENT_COUNT );

                _defaultTest( heap, ELEMENT_COUNT );
            }

            [Test]
            public void BruteForceTest()
            {
                _fillHeapWithChecks( new BinaryHeap<int>(), 10000 ); 
            }

            [Test]
            public void TestDequeue()
            { 
                BinaryHeap<int> heap = new BinaryHeap<int>();
                _fillHeap( heap, 10000 );
                _testValueOrder( heap );
            }

            [Test]
            public void TestClear()
            {
                const int ELEMENT_COUNT = 10000;
                BinaryHeap<int> heap = new BinaryHeap<int>();

                _fillHeap( heap, ELEMENT_COUNT );

                Assert.That( ELEMENT_COUNT, Is.EqualTo( heap.Count ) );

                heap.Clear();

                Assert.That( 0, Is.EqualTo( heap.Count ) );
                Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
            }

            [Test]
            public void TestTrimExcess()
            {
                const int ELEMENT_COUNT = 1000;
                const int INITIAL_CAPACITY = 2000;
                BinaryHeap<int> heap = new BinaryHeap<int>( INITIAL_CAPACITY );

                _fillHeap( heap, ELEMENT_COUNT );

                Assert.That( INITIAL_CAPACITY, Is.EqualTo( heap.Capacity ) );

                heap.TrimExcess();

                Assert.That( ELEMENT_COUNT, Is.EqualTo( heap.Capacity ) );
                Assert.That( ELEMENT_COUNT, Is.EqualTo( heap.Count ) );

                Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
            }

            [Test]
            public void TestContains()
            {
                const int ELEMENT_COUNT = 1000;

                var r = new Random( (int) System.DateTime.Now.Ticks );

                HashSet<int> contained = new HashSet<int>();
                HashSet<int> notContained = new HashSet<int>();

                while ( contained.Count < ELEMENT_COUNT )
                {
                    contained.Add( r.Next() );
                }

                while ( notContained.Count < ELEMENT_COUNT )
                {
                    int value = r.Next();

                    if ( !contained.Contains( value ) )
                    {
                        notContained.Add( value );
                    }
                }

                BinaryHeap<int> heap = new BinaryHeap<int>( contained );

                foreach ( int value in contained )
                {
                    Assert.That( heap.Contains( value ) );
                }

                foreach ( int value in notContained )
                {
                    Assert.That( heap.Contains( value ), Is.False );
                }

                Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
            }

            [Test]
            public void TestEnumerator()
            {
                const int ELEMENT_COUNT = 1000;

                var r = new Random( (int) System.DateTime.Now.Ticks );

                HashSet<int> values = new HashSet<int>();

                for ( int i = 0; i < ELEMENT_COUNT; ++i )
                {
                    values.Add( r.Next() );
                }

                BinaryHeap<int> heap = new BinaryHeap<int>( values );

                Assert.That( values.Count, Is.EqualTo( heap.Count ) );
                Assert.That( values.Except( heap ).Count() == 0 );
                Assert.That( heap.Except( values ).Count() == 0 );
                Assert.That( BinaryHeap<int>.VerifyHeapProperty( heap ) );
            }


            [Test]
            public void TestRemove()
            {
                const int ELEMENT_COUNT = 10000;

                var r = new Random( (int) System.DateTime.Now.Ticks );

                List<int> values = new List<int>();

                for ( int i = 0; i < ELEMENT_COUNT; ++i )
                {
                    values.Add( r.Next() );
                }

                BinaryHeap<int> heap = new BinaryHeap<int>( values );

                for ( int i = 7; i < ELEMENT_COUNT; i += 3 )
                {
                    int oldCount = heap.Count;

                    Assert.That( heap.Remove( values[i] ) );
                    Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );

                    Assert.That( heap.Count == oldCount - 1 );
                }

                _testValueOrder( heap );
            }

            [Test]
            public void TestRemoveEqualValues()
            {
                const int ELEMENT_COUNT = 10000;

                List<int> values = new List<int>();

                for ( int i = 0; i < ELEMENT_COUNT; ++i )
                {
                    values.Add( 10 );
                }

                BinaryHeap<int> heap = new BinaryHeap<int>( values );

                for ( int i = 7; i < ELEMENT_COUNT; i += 7 )
                {
                    int oldCount = heap.Count;

                    Assert.That( heap.Remove( values[i] ) );
                    Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );

                    Assert.That( heap.Count == oldCount - 1 );
                }

                _testValueOrder( heap );
            }

            [Test]
            public void TestRemoveAll()
            {
                const int ITERATIONS = 100;

                for ( int iteration = 0; iteration < ITERATIONS; ++iteration )
                {
                    const int ELEMENT_COUNT = 10000;

                    var r = new Random( (int) System.DateTime.Now.Ticks );

                    List<int> values = new List<int>();

                    for ( int i = 0; i < ELEMENT_COUNT; ++i )
                    {
                        values.Add( r.Next() );
                    }

                    int unevenCount = values.Count( x => x % 2 == 1 );
                    int evenCount = values.Count( x => x % 2 == 0 );

                    Assert.That( values.Count == unevenCount + evenCount );

                    BinaryHeap<int> heap = new BinaryHeap<int>( values );

                    Assert.That( heap.Count == values.Count );

                    heap.RemoveAll( x => x % 2 == 1 );

                    Assert.That( heap.Count == evenCount );
                    Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
                }
            }

            private static void _defaultTest( BinaryHeap<int> heap, int elementCount )
            {
                _fillHeap( heap, elementCount );
                Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
            }

            private static void _testValueOrder( BinaryHeap<int> heap )
            {
                List<int> values = new List<int>();
                while ( heap.Count != 0 )
                {
                    values.Add( heap.Dequeue() );
                }

                for ( int i = 1; i < values.Count; ++i )
                {
                    Assert.That( values[i - 1] > values[i], Is.False );
                }
            }

            private static void _fillHeap( BinaryHeap<int> heap, int elementCount )
            {
                var r = new Random( (int) System.DateTime.Now.Ticks );

                for ( int i = 0; i < elementCount; ++i )
                {
                    if ( heap.Count != 0 && r.NextDouble() < 0.33 )
                    {
                        heap.Dequeue();
                    }
                    else
                    {
                        heap.Enqueue( r.Next() );
                    }
                }

                while ( heap.Count < elementCount )
                {
                    int oldCount = heap.Count;
                    heap.Enqueue( r.Next() );
                }
            }

            private static void _fillHeapWithChecks( BinaryHeap<int> heap, int elementCount )
            {
                var r = new Random( (int)System.DateTime.Now.Ticks );

                for ( int i = 0; i < elementCount; ++i )
                {
                    if ( heap.Count != 0 && r.NextDouble() < 0.33 )
                    {
                        int oldCount = heap.Count;
                        heap.Dequeue();

                        Assert.That( oldCount == heap.Count + 1 );
                    }
                    else
                    {
                        int oldCount = heap.Count;

                        heap.Enqueue( r.Next() );

                        Assert.That( oldCount == heap.Count - 1 );
                    }

                    Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
                }

                while ( heap.Count < elementCount )
                {
                    int oldCount = heap.Count;
                    heap.Enqueue( r.Next() );

                    Assert.That( oldCount == heap.Count - 1 );
                    Assert.That( BinaryHeap<int>.FullIntegrityCheck( heap ) );
                }
            }
        }
    }
    #endif

    #endregion
}